The present work determines the exact nature of {\em linear time computable}notions which characterise automatic functions (those whose graphs arerecognised by a finite automaton). The paper also determines which type oflinear time notions permit full learnability for learning in the limit ofautomatic classes (families of languages which are uniformly recognised by afinite automaton). In particular it is shown that a function is automatic iffthere is a one-tape Turing machine with a left end which computes the functionin linear time where the input before the computation and the output after thecomputation both start at the left end. It is known that learners realised asautomatic update functions are restrictive for learning. In the present work itis shown that one can overcome the problem by providing work tapes additionalto a resource-bounded base tape while keeping the update-time to be linear inthe length of the largest datum seen so far. In this model, one additional suchwork tape provides additional learning power over the automatic learner modeland two additional work tapes give full learning power. Furthermore, one canalso consider additional queues or additional stacks in place of additionalwork tapes and for these devices, one queue or two stacks are sufficient forfull learning power while one stack is insufficient.
展开▼
